package com.yangzhe.algorithm.c032;

import java.util.HashSet;

// 位图的实现

public class Code01_Bitset {

    /**
     * 位图实现
     * 位图可以存储一段连续的数字，此实现存储 从0 至 num -1个数字
     * 数字在第几个int = num / 32
     * 数字在int中第几位 = num % 32
     */
    public static class Bitset {
        public int[] set;

        /**
         * 初始化 位图
         * 一个int可以代表 32 个数字
         * 需要多少个int 使用 向上取整 (n / 32)
         *
         * @param n 位图的大小
         */
        public Bitset(int n) {
            // 正整数相除向上取整的方法 (a + b - 1) / b
            int intCount = (n + 31) / 32;
            set = new int[intCount];
        }

        /**
         * 将一个数字添加到位图中
         * <p>
         * 将第 n 位修改为 1 的方法，这个数字 | (1 << n)
         *
         * @param num num 不能大于位图的范围
         */
        public void add(int num) {
            set[num / 32] |= 1 << num % 32;
        }

        /**
         * 将一个数字从位图中删除
         * <p>
         * 将第 n 位修改为 0 的方法， 这个数字 & ~( 1 << n)
         *
         * @param num num 不能大于位图的范围
         */
        public void remove(int num) {
            set[num / 32] &= ~(1 << num % 32);
        }

        /**
         * 如果数字存在则删除，不存在则添加
         *
         * @param num num 不能大于位图的范围
         */
        public void reverse(int num) {
            set[num / 32] ^= 1 << num % 32;
        }

        public boolean contains(int num) {
            return (set[num / 32] & 1 << num % 32) != 0;
        }

    }

    // 对数器测试
    public static void main(String[] args) {
        int n = 1000;
        int testTimes = 10000;
        System.out.println("测试开始");
        // 实现的位图结构
        Bitset bitSet = new Bitset(n);
        // 直接用HashSet做对比测试
        HashSet<Integer> hashSet = new HashSet<>();
        System.out.println("调用阶段开始");
        for (int i = 0; i < testTimes; i++) {
            double decide = Math.random();
            // number -> 0 ~ n-1，等概率得到
            int number = (int) (Math.random() * n);
            if (decide < 0.333) {
                bitSet.add(number);
                hashSet.add(number);
            } else if (decide < 0.666) {
                bitSet.remove(number);
                hashSet.remove(number);
            } else {
                bitSet.reverse(number);
                if (hashSet.contains(number)) {
                    hashSet.remove(number);
                } else {
                    hashSet.add(number);
                }
            }
        }
        System.out.println("调用阶段结束");
        System.out.println("验证阶段开始");
        for (int i = 0; i < n; i++) {
            if (bitSet.contains(i) != hashSet.contains(i)) {
                System.out.println("出错了!");
            }
        }
        System.out.println("验证阶段结束");
        System.out.println("测试结束");
    }

}
